DFS—Cycle Detection Code (Undirected)

This Python code provides a practical implementation of the cycle detection algorithm.

The main function, has_cycle_undirected, iterates through all nodes to handle potentially disconnected graphs.
A nested helper function, go(u, p), performs the actual DFS traversal, carrying the current node `u` and its parent `p`.
Passing the parent `p` is crucial to avoid immediately identifying the edge used to arrive at `u` as a back edge.
A cycle is confirmed when the traversal encounters a visited neighbor `w` that is not the direct parent `p`.
The function returns `True` as soon as the first cycle is found, providing an efficient check for the entire graph.

def has_cycle_undirected(G):
    visited = set()
    def go(u, p):
        visited.add(u)
        for w in G[u]:
            if w not in visited:
                if go(w, u): return True
            elif w != p:
                return True
        return False
    for s in G:
        if s not in visited:
            if go(s, None): return True
    return False